The present invention is a method and apparatus utilizing automated semantic pattern recognition whereby a user of an instruction or repair manual enters a query regarding information in the text of the manual and the invention displays the locations in the text of information responsive to the query. Although the invention is described in terms of its implementation as an aid to a user of a manual, many of the most important features of the invention have general application and are not intended to be limited to text in a manual format.
Repair persons or users of a piece of equipment often turn to a manual for instructions regarding operation, maintenance of repair. The repair person or user typically must probe the table of contents and the index for relevant words that might point to relevant pages in the text. Although effective, this method is time consuming. Search time frequently is an important constraint, such as when a customer service representative needs to respond quickly to questions from customers over the telephone.
The present invention uses semantic pattern recognition to rapidly locate relevant information in the text of a user manual. Semantic pattern recognition has long been thought of as a possible solution for improving text and information retrieval. Unfortunately, most natural language understanding systems have lacked the lexical and semantic depth necessary for handling the broad range of semantic situations typically encountered as part of daily human activities. However, there are some areas where a language-oriented method of organization and comparison is quite useful. One such domain encompasses information that can be organized topically into subject categories. A prime example of topical organization is the typical user or repair manual, which is divided into sections by topic and uses terse explanations comprised of highly descriptive words and phrases.
The present invention locates information in the natural language text of a manual using a computer that includes a video monitor and a memory device for storing a data structure representing the natural language text. The data structure has the form of a tree structure having nodes arranged at different levels of the tree structure, wherein each node represents information from associated locations in the text, each location having a corresponding location identifier, such as a page or section number. Each node contains node constituents representing words or phrases from the text, and each node may be represented by a vector comprising node constituents as elements. The parsing of text into its contextually related constituents is well known in the art.
Typically, the nodes at higher levels of the tree represent general categories of information. Nodes at succeedingly lower levels in the tree usually represent succeedingly more specific categorical subsets of the general categories of information represented at the higher levels. For example, nodes at one level may represent chapter headings from a manual, while nodes at the next level may represent sections within a chapter, and nodes at the subsequent level may represent subsections thereof. Accordingly, a node at one level in the tree is referred to as a "parent" node, while a node at a level immediately below the parent node and representing a categorical subset of the information represented by the parent node is referred to as a "child" node of that parent. The parent node and other nodes at the higher levels of the tree representing more general categories of information than a particular child node are referred to as the "ancestors" of that child node.
The present invention takes advantage of contextual propagation from the ancestors of a node to determine with a given degree of certainty whether the node contains information responsive to a query. The query is entered by a user or otherwise input into the system in the hope that the natural language text contains the answer to the query. The query is formatted into a query data structure. The query data structure is compared to a node to produce a comparison value representative of the degree of similarity between the query and the information represented by the node. The comparison value is enhanced by an amount representative of the degree of similarity between the query and the information represented by ancestors of the node to produce an enhanced comparison value. If the enhanced comparison value exceeds a predetermined lower bound and the node contributes information responsive to the query, then the location identifiers associated with the node are stored in memory. The process of comparing the query data structure to a node, enhancing the comparison value and storing the location identifiers is repeated at each node in the tree structure. After these steps have been performed for the entire tree structure, the stored location identifiers are displayed on the video monitor.
Note that the present invention tests whether the node contributes information responsive to the query in addition to determining whether the enhanced comparison value exceeds a predetermined lower bound. Because the enhanced comparison value represents the inclusion of information from ancestor nodes, the enhanced comparison value may exceed the lower bound based solely on the degree of similarity between the query and the information represented by the ancestors of the node, even if there is no match at all between the current node and the query. Accordingly, it is necessary to test whether the current node contains at least some information responsive to the query.
In one embodiment, the query is formatted into a query data structure having query constituents that are similar in format to the node constituents of the text data structure. That is, each query constituent represents a word or phrase contained in the query. The query data structure is compared to a node in the tree to produce a match vector having a number of match elements, the match vector being representative of the degree of similarity between the query data structure and the node. Each match element corresponds in position to one of the query constituents and to one of the elements of a parent vector, the parent vector having been initialized to zero.
The resulting match vector is merged with the parent vector by comparing each parent vector element to each corresponding match element to produce a merge vector having a number of merge elements, each merge element corresponding in position to a parent element, and by setting each merge element to be equal to the greater of the corresponding parent element and the corresponding match element.
A contribution flag is set to true if any of the match elements is greater than zero and, at the same time, greater than or equal to the parent element corresponding to that match element. If the contribution flag has been set to true, then: (1) the merge elements are averaged to produce a merge vector average; and (2) if the merge vector average equals or exceeds a predetermined threshold value, then the location identifiers associated with the node are stored for display. Note that the terms "enhanced comparison value" and "lower bound" were used above when referring to the invention in its broadest sense. In this particular embodiment, the merge vector average serves as the enhanced companion value and the threshold value as the lower bound.
Whether the contribution flag has been set to true or not, the invention repeats the process of producing the match vector, merging the match vector with the parent vector, determining whether to set the contribution flag, and, if the contribution flag is set to true, averaging the merge elements and storing the relevant location identifiers, wherein all of these steps are performed at each node after substituting for the parent vector the merge vector that resulted from performing the merging step on the parent node of the node under examination. After these steps have been performed at each node in the data structure, then the stored location identifiers are displayed on the video monitor.
The foregoing summary demonstrates that through the merging process, the invention takes advantage of the contextual propagation of comparison properties to a node from its ancestors in the tree structure. Instead of just comparing the match value to the threshold, the invention compares a new value representative of the degree of similarity not only of the present node to the query, but also of the degree of similarity between the ancestors of the present node and the query. Thus, a node which might otherwise not pass the threshold would be counted as containing relevant information because it has inherited comparison traits from its ancestors.